home *** CD-ROM | disk | FTP | other *** search
/ Just Call Me Internet / Just Call Me Internet.iso / prog / atari / c / nos042_s / slcomp.c < prev    next >
C/C++ Source or Header  |  1994-09-16  |  13KB  |  488 lines
  1. /*
  2.  * Routines to compress and uncompess tcp packets (for transmission
  3.  * over low speed serial lines.
  4.  *
  5.  * Copyright (c) 1989 Regents of the University of California.
  6.  * All rights reserved.
  7.  *
  8.  * Redistribution and use in source and binary forms are permitted
  9.  * provided that the above copyright notice and this paragraph are
  10.  * duplicated in all such forms and that any documentation,
  11.  * advertising materials, and other materials related to such
  12.  * distribution and use acknowledge that the software was developed
  13.  * by the University of California, Berkeley.  The name of the
  14.  * University may not be used to endorse or promote products derived
  15.  * from this software without specific prior written permission.
  16.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  17.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  18.  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  19.  *
  20.  *    Van Jacobson (van@helios.ee.lbl.gov), Dec 31, 1989:
  21.  *    - Initial distribution.
  22.  */
  23. /*
  24.  * modified for KA9Q Internet Software Package by
  25.  * Katie Stevens (dkstevens@ucdavis.edu)
  26.  * University of California, Davis
  27.  * Computing Services
  28.  *    - 01-31-90    initial adaptation (from 1.19)
  29.  *    PPP.05    02-15-90 [ks]
  30.  *    PPP.08    05-02-90 [ks]    use PPP protocol field to signal compression
  31.  *    PPP.15    09-90     [ks]    improve mbuf handling
  32.  *    PPP.16  11-02     [karn]    substantially rewritten to use NOS facilities
  33.  *
  34.  * ATARI Version by David Nash - dnash@chaos.demon.co.uk
  35.  *
  36.  * cond out mem.h
  37.  */
  38.  
  39. #ifndef ATARI
  40. #include <mem.h>
  41. #endif
  42.  
  43. #include "global.h"
  44. #include "mbuf.h"
  45. #include "tcp.h"
  46. #include "ip.h"
  47. #include "internet.h"
  48. #include "slcomp.h"
  49.  
  50. static char *encode __ARGS((char *cp,int16 n));
  51. static long decode __ARGS((struct mbuf **bufp));
  52.  
  53. void
  54. sl_compress_init(comp)
  55. struct slcompress *comp;
  56. {
  57.     register int16 i;
  58.     register struct cstate *tstate = comp->tstate;
  59.  
  60.     memset((char *)comp, 0, sizeof(*comp));
  61.     for(i = MAX_STATES - 1; i > 0; --i){
  62.         tstate[i].cs_id = i;
  63.         tstate[i].cs_next = &tstate[i - 1];
  64.     }
  65.     tstate[0].cs_next = &tstate[MAX_STATES - 1];
  66.     tstate[0].cs_id = 0;
  67.     comp->last_cs = &tstate[0];
  68.     comp->last_recv = 255;
  69.     comp->last_xmit = 255;
  70. }
  71.  
  72. /* Encode a number */
  73. static char *encode(
  74.         char *cp,
  75.         int16 n)
  76. {
  77.     if(n >= 256 || n == 0){
  78.         *cp++ = 0;
  79.         cp = put16(cp,n);
  80.     } else {
  81.         *cp++ = n;
  82.     }
  83.     return cp;
  84. }
  85.  
  86. /* Decode a number */
  87. static long
  88. decode(bufp)
  89. struct mbuf **bufp;
  90. {
  91.     register int x;
  92.  
  93.     x = PULLCHAR(bufp);
  94.     if(x == 0){
  95.         return pull16(bufp);    /* pull16 returns -1 on error */
  96.     } else {
  97.         return (long)x;        /* -1 if PULLCHAR returned error */
  98.     }
  99. }
  100.  
  101. int
  102. sl_compress_tcp(bpp,comp, compress_cid)
  103. struct mbuf **bpp;
  104. struct slcompress *comp;
  105. int compress_cid;
  106. {
  107.     register struct cstate *cs = comp->last_cs->cs_next;
  108.     register int16 hlen;
  109.     register struct tcp *oth;
  110.     register unsigned long deltaS, deltaA;
  111.     register int16 changes = 0;
  112.     char new_seq[16];
  113.     register char *cp = new_seq;
  114.     struct mbuf *bp;
  115.     struct tcp th;
  116.     struct ip iph;
  117.  
  118.     /* Extract IP header */
  119.     hlen = ntohip(&iph,bpp);
  120.  
  121.     /* Bail if this packet isn't TCP, or is an IP fragment */
  122.     if(iph.protocol != TCP_PTCL || iph.offset != 0 || iph.flags.mf){
  123.         /* Send as regular IP */
  124.         if(iph.protocol != TCP_PTCL)
  125.             comp->sls_nontcp++;
  126.         else
  127.             comp->sls_asistcp++;
  128.         *bpp = htonip(&iph,*bpp,1);
  129.         return SL_TYPE_IP;
  130.     }
  131.     /* Extract TCP header */
  132.     hlen += ntohtcp(&th,bpp);
  133.  
  134.     /*  Bail if the TCP packet isn't `compressible' (i.e., ACK isn't set or
  135.      *  some other control bit is set).
  136.      */
  137.     if(th.flags.syn || th.flags.fin || th.flags.rst || !th.flags.ack){
  138.         /* TCP connection stuff; send as regular IP */
  139.         comp->sls_asistcp++;
  140.         *bpp = htontcp(&th,*bpp,NULLHEADER);
  141.         *bpp = htonip(&iph,*bpp,1);
  142.         return SL_TYPE_IP;
  143.     }
  144.     /*
  145.      * Packet is compressible -- we're going to send either a
  146.      * COMPRESSED_TCP or UNCOMPRESSED_TCP packet.  Either way we need
  147.      * to locate (or create) the connection state.  Special case the
  148.      * most recently used connection since it's most likely to be used
  149.      * again & we don't have to do any reordering if it's used.
  150.      */
  151.     if(iph.source != cs->cs_ip.source ||
  152.      iph.dest  != cs->cs_ip.dest ||
  153.      th.source != cs->cs_tcp.source ||
  154.      th.dest != cs->cs_tcp.dest){
  155.         /*
  156.          * Wasn't the first -- search for it.
  157.          *
  158.          * States are kept in a circularly linked list with
  159.          * last_cs pointing to the end of the list.  The
  160.          * list is kept in lru order by moving a state to the
  161.          * head of the list whenever it is referenced.  Since
  162.          * the list is short and, empirically, the connection
  163.          * we want is almost always near the front, we locate
  164.          * states via linear search.  If we don't find a state
  165.          * for the datagram, the oldest state is (re-)used.
  166.          */
  167.         register struct cstate *lcs;
  168.         register struct cstate *lastcs = comp->last_cs;
  169.  
  170.         do {
  171.             lcs = cs; cs = cs->cs_next;
  172.             comp->sls_searches++;
  173.             if(iph.source == cs->cs_ip.source
  174.              && iph.dest == cs->cs_ip.dest
  175.              && th.source == cs->cs_tcp.source
  176.              && th.dest == cs->cs_tcp.dest)
  177.                 goto found;
  178.         } while(cs != lastcs);
  179.  
  180.         /*
  181.          * Didn't find it -- re-use oldest cstate.  Send an
  182.          * uncompressed packet that tells the other side what
  183.          * connection number we're using for this conversation.
  184.          * Note that since the state list is circular, the oldest
  185.          * state points to the newest and we only need to set
  186.          * last_cs to update the lru linkage.
  187.          */
  188.         comp->sls_misses++;
  189.         comp->last_cs = lcs;
  190.  
  191.         goto uncompressed;
  192.  
  193.     found:
  194.         /*
  195.          * Found it -- move to the front on the connection list.
  196.          */
  197.         if(cs == lastcs)
  198.             comp->last_cs = lcs;
  199.         else {
  200.             lcs->cs_next = cs->cs_next;
  201.             cs->cs_next = lastcs->cs_next;
  202.             lastcs->cs_next = cs;
  203.         }
  204.     }
  205.  
  206.     /*
  207.      * Make sure that only what we expect to change changed.
  208.      * Check the following:
  209.      * IP protocol version, header length & type of service.
  210.      * The "Don't fragment" bit.
  211.      * The time-to-live field.
  212.      * The TCP header length.
  213.      * IP options, if any.
  214.      * TCP options, if any.
  215.      * If any of these things are different between the previous &
  216.      * current datagram, we send the current datagram `uncompressed'.
  217.      */
  218.     oth = &cs->cs_tcp;
  219.  
  220.     if(iph.version != cs->cs_ip.version || iph.optlen != cs->cs_ip.optlen
  221.      || iph.tos != cs->cs_ip.tos
  222.      || iph.flags.df != cs->cs_ip.flags.df
  223.      || iph.ttl != cs->cs_ip.ttl
  224.      || th.optlen != cs->cs_tcp.optlen
  225.      || iph.optlen != cs->cs_ip.optlen
  226.      || (iph.optlen > 0 && memcmp(iph.options,cs->cs_ip.options,iph.optlen) != 0)
  227.      || (th.optlen > 0 && memcmp(th.options,cs->cs_tcp.options,th.optlen) != 0)){
  228.         goto uncompressed;
  229.     }
  230.     /*
  231.      * Figure out which of the changing fields changed.  The
  232.      * receiver expects changes in the order: urgent, window,
  233.      * ack, seq (the order minimizes the number of temporaries
  234.      * needed in this section of code).
  235.      */
  236.     if(th.flags.urg){
  237.         deltaS = th.up;
  238.         cp = encode(cp,deltaS);
  239.         changes |= NEW_U;
  240.     } else if(th.up != oth->up){
  241.         /* argh! URG not set but urp changed -- a sensible
  242.          * implementation should never do this but RFC793
  243.          * doesn't prohibit the change so we have to deal
  244.          * with it. */
  245.         goto uncompressed;
  246.     }
  247.     if((deltaS = th.wnd - oth->wnd) != 0){
  248.         cp = encode(cp,deltaS);
  249.         changes |= NEW_W;
  250.     }
  251.     if((deltaA = th.ack - oth->ack) != 0L){
  252.         if(deltaA > 0x0000ffff)
  253.             goto uncompressed;
  254.         cp = encode(cp,deltaA);
  255.         changes |= NEW_A;
  256.     }
  257.     if((deltaS = th.seq - oth->seq) != 0L){
  258.         if(deltaS > 0x0000ffff)
  259.             goto uncompressed;
  260.         cp = encode(cp,deltaS);
  261.         changes |= NEW_S;
  262.     }
  263.  
  264.     switch(changes){
  265.     case 0:    /* Nothing changed. If this packet contains data and the
  266.          * last one didn't, this is probably a data packet following
  267.          * an ack (normal on an interactive connection) and we send
  268.          * it compressed.  Otherwise it's probably a retransmit,
  269.          * retransmitted ack or window probe.  Send it uncompressed
  270.          * in case the other side missed the compressed version.
  271.          */
  272.         if(iph.length != cs->cs_ip.length && cs->cs_ip.length == hlen)
  273.             break;
  274.         goto uncompressed;
  275.     case SPECIAL_I:
  276.     case SPECIAL_D:
  277.         /* actual changes match one of our special case encodings --
  278.          * send packet uncompressed.
  279.          */
  280.         goto uncompressed;
  281.     case NEW_S|NEW_A:
  282.         if(deltaS == deltaA &&
  283.             deltaS == cs->cs_ip.length - hlen){
  284.             /* special case for echoed terminal traffic */
  285.             changes = SPECIAL_I;
  286.             cp = new_seq;
  287.         }
  288.         break;
  289.     case NEW_S:
  290.         if(deltaS == cs->cs_ip.length - hlen){
  291.             /* special case for data xfer */
  292.             changes = SPECIAL_D;
  293.             cp = new_seq;
  294.         }
  295.         break;
  296.     }
  297.     deltaS = iph.id - cs->cs_ip.id;
  298.     if(deltaS != 1){
  299.         cp = encode(cp,deltaS);
  300.         changes |= NEW_I;
  301.     }
  302.     if(th.flags.psh)
  303.         changes |= TCP_PUSH_BIT;
  304.     /* Grab the cksum before we overwrite it below.  Then update our
  305.      * state with this packet's header.
  306.      */
  307.     deltaA = th.checksum;
  308.     ASSIGN(cs->cs_ip,iph);
  309.     ASSIGN(cs->cs_tcp,th);
  310.     /* We want to use the original packet as our compressed packet.
  311.      * (cp - new_seq) is the number of bytes we need for compressed
  312.      * sequence numbers.  In addition we need one byte for the change
  313.      * mask, one for the connection id and two for the tcp checksum.
  314.      * So, (cp - new_seq) + 4 bytes of header are needed.
  315.      */
  316.     deltaS = cp - new_seq;
  317.     if(compress_cid == 0 || comp->last_xmit != cs->cs_id){
  318.         bp = *bpp = pushdown(*bpp,deltaS + 4);
  319.         cp = bp->data;
  320.         *cp++ = changes | NEW_C;
  321.         *cp++ = cs->cs_id;
  322.     } else {
  323.         bp = *bpp = pushdown(*bpp,deltaS + 3);
  324.         cp = bp->data;
  325.         *cp++ = changes;
  326.     }
  327.     cp = put16(cp,(int16)deltaA);    /* Write TCP checksum */
  328.     memcpy(cp,new_seq,deltaS);    /* Write list of deltas */
  329.     comp->sls_compressed++;
  330.     return SL_TYPE_COMPRESSED_TCP;
  331.  
  332.     /* Update connection state cs & send uncompressed packet (i.e.,
  333.      * a regular ip/tcp packet but with the 'conversation id' we hope
  334.      * to use on future compressed packets in the protocol field).
  335.      */
  336. uncompressed:
  337.     iph.protocol = cs->cs_id;
  338.     ASSIGN(cs->cs_ip,iph);
  339.     ASSIGN(cs->cs_tcp,th);
  340.     comp->last_xmit = cs->cs_id;
  341.     comp->sls_uncompressed++;
  342.     *bpp = htontcp(&th,*bpp,NULLHEADER);
  343.     *bpp = htonip(&iph,*bpp,1);
  344.     return SL_TYPE_UNCOMPRESSED_TCP;
  345. }
  346.  
  347.  
  348. int sl_uncompress_tcp(
  349.         struct mbuf **bufp,
  350.         int      len,
  351.         int16  type,
  352.         struct slcompress *comp)
  353. {
  354.     int changes;
  355.     long x;
  356.     register struct tcp *thp;
  357.     register struct cstate *cs;
  358.     struct ip iph;
  359.     struct tcp th;
  360.  
  361.     switch(type){
  362.     case SL_TYPE_UNCOMPRESSED_TCP:
  363.         /* Extract IP and TCP headers and verify conn ID */
  364.         ntohip(&iph,bufp);
  365.         ntohtcp(&th,bufp);
  366.         if(uchar(iph.protocol) >= MAX_STATES)
  367.             goto bad;
  368.  
  369.         /* Update local state */
  370.         cs = &comp->rstate[comp->last_recv = uchar(iph.protocol)];
  371.         comp->flags &=~ SLF_TOSS;
  372.         iph.protocol = TCP_PTCL;
  373.         ASSIGN(cs->cs_ip,iph);
  374.         ASSIGN(cs->cs_tcp,th);
  375.  
  376.         /* Put headers back on packet
  377.          * Neither header checksum is recalculated
  378.          */
  379.         *bufp = htontcp(&th,*bufp,NULLHEADER);
  380.         *bufp = htonip(&iph,*bufp,1);
  381.         comp->sls_uncompressedin++;
  382.         return len;
  383.  
  384.     default:
  385.         goto bad;
  386.  
  387.     case SL_TYPE_COMPRESSED_TCP:
  388.         break;
  389.     }
  390.     /* We've got a compressed packet; read the change byte */
  391.     comp->sls_compressedin++;
  392.     if(len < 3){
  393.         comp->sls_errorin++;
  394.         return 0;
  395.     }
  396.     changes = PULLCHAR(bufp);    /* "Can't fail" */
  397.     if(changes & NEW_C){
  398.         /* Make sure the state index is in range, then grab the state.
  399.          * If we have a good state index, clear the 'discard' flag.
  400.          */
  401.         x = PULLCHAR(bufp);    /* Read conn index */
  402.         if(x < 0 || x >= MAX_STATES)
  403.             goto bad;
  404.  
  405.         comp->flags &=~ SLF_TOSS;
  406.         comp->last_recv = x;
  407.     } else {
  408.         /* this packet has an implicit state index.  If we've
  409.          * had a line error since the last time we got an
  410.          * explicit state index, we have to toss the packet. */
  411.         if(comp->flags & SLF_TOSS){
  412.             comp->sls_tossed++;
  413.             return 0;
  414.         }
  415.     }
  416.     cs = &comp->rstate[comp->last_recv];
  417.     thp = &cs->cs_tcp;
  418.     
  419.     if((x = pull16(bufp)) == -1)    /* Read the TCP checksum */
  420.         goto bad; 
  421.     thp->checksum = x;
  422.  
  423.     thp->flags.psh = (changes & TCP_PUSH_BIT) ? 1 : 0;
  424.  
  425.     switch(changes & SPECIALS_MASK){
  426.     case SPECIAL_I:        /* Echoed terminal traffic */
  427.         {
  428.         register int16 i;
  429.         i = cs->cs_ip.length;
  430.         i -= (cs->cs_ip.optlen + IPLEN + TCPLEN);
  431.         thp->ack += i;
  432.         thp->seq += i;
  433.         }
  434.         break;
  435.  
  436.     case SPECIAL_D:            /* Unidirectional data */
  437.         thp->seq += cs->cs_ip.length - (cs->cs_ip.optlen +IPLEN + TCPLEN);
  438.         break;
  439.  
  440.     default:
  441.         if(changes & NEW_U){
  442.             thp->flags.urg = 1;
  443.             if((x = decode(bufp)) == -1)
  444.                 goto bad;
  445.             thp->up = x;
  446.         } else
  447.             thp->flags.urg = 0;
  448.         if(changes & NEW_W){
  449.             if((x = decode(bufp)) == -1)
  450.                 goto bad;
  451.             thp->wnd += x;
  452.         }
  453.         if(changes & NEW_A){
  454.             if((x = decode(bufp)) == -1)
  455.                 goto bad;
  456.             thp->ack += x;
  457.         }
  458.         if(changes & NEW_S){
  459.             if((x = decode(bufp)) == -1)
  460.                 goto bad;
  461.             thp->seq += x;
  462.         }
  463.         break;
  464.     }
  465.     if(changes & NEW_I){
  466.         if((x = decode(bufp)) == -1)
  467.             goto bad;
  468.         cs->cs_ip.id += x;
  469.     } else
  470.         cs->cs_ip.id++;
  471.  
  472.     /*
  473.      * At this point, bufp points to the first byte of data in the
  474.      * packet.  Put the reconstructed TCP and IP headers back on the
  475.      * packet.
  476.      */
  477.     len = len_p(*bufp) + IPLEN + TCPLEN + cs->cs_ip.optlen;
  478.     cs->cs_ip.length = len;
  479.  
  480.     *bufp = htontcp(thp,*bufp,NULLHEADER);
  481.     *bufp = htonip(&cs->cs_ip,*bufp,0);
  482.     return len;
  483. bad:
  484.     comp->flags |= SLF_TOSS;
  485.     comp->sls_errorin++;
  486.     return 0;
  487. }
  488.